#include <list>
#include <iostream>
#include <initializer_list>
namespace mini_stl
{
    template <class T>
    struct list_node
    {
        struct list_node<T> *next_;
        struct list_node<T> *prev_;
        T data_;
        list_node(const T &val = T())
            : data_(val), next_(nullptr), prev_(nullptr)
        {
        }
        ~list_node()
        {
        }
    };

    template <class T, class Ptr, class Ref>
    struct list_iterator
    {
        typedef list_node<T> Node;
        typedef list_iterator<T, Ptr, Ref> Self;
        Node *node_;

        list_iterator(Node *node)
            : node_(node)
        {
        }

        // 编译器优化  operator->(iterator) ->
        Ptr operator->()
        {
            return &(node_->data_);
        }

        Ref operator*()
        {
            return node_->data_;
        }

        // 前置++
        Self &operator++()
        {
            node_ = node_->next_;
            return *this;
        }

        // 后置++
        Self operator++(int)
        {
            Node *tmp = node_;
            node_ = node_->next_;
            return list_iterator(tmp);
        }

        // 前置--
        Self &operator--()
        {
            node_ = node_->prev_;
            return *this;
        }

        // 后置--
        Self operator--(int)
        {
            Node *tmp = node_;
            node_ = node_->prev_;
            return list_iterator(tmp);
        }

        bool operator!=(const list_iterator &rhs)
        {
            return node_ != rhs.node_;
        }

        bool operator==(const list_iterator &rhs)
        {
            return node_ == rhs.node_;
        }
    };

    template <class T>
    class list
    {
        typedef list_iterator<T, T *, T &> iterator;
        typedef list_iterator<T, const T *, const T &> const_iterator;
        typedef list_node<T> Node;

    public:
        list()
        {
            init();
        }

        list(const list<T> &l)
        {
            auto iter = l.cbegin();
            while (iter != l.cend())
            {
                emplace_back(*iter);
            }
        }

        list(list<T> &&l)
        {
            auto iter = l.cbegin();
            while (iter != l.cend())
            {
                emplace_back(*iter);
            }
        }

        template <class InputIterator>
        list(InputIterator begin, InputIterator end)
        {
            while (begin != end)
            {
                emplace_back(*begin++);
            }
        }

        list(const std::initializer_list<T> &init_list)
        {
            init();
            for (auto &item : init_list)
            {
                emplace_back(item);
            }
        }

        list(size_t n, const T &val = T())
        {
            init();
            while (n--)
            {
                emplace_back(val);
            }
        }

        iterator insert(iterator pos, const T &val = T())
        {
            Node *newnode = new Node(val);
            Node *prev = pos.node_->prev_;
            Node *next = pos.node_;
            prev->next_ = newnode;
            newnode->prev_ = prev;
            next->prev_ = newnode;
            newnode->next_ = next;
            return iterator(newnode);
        }

        void push_back(const T &val = T())
        {
            insert(end(), val);
        }

        void push_back(const T &&val)
        {
            insert(end(), val);
        }

        template <typename... Args>
        iterator emplace_back(Args &&...args)
        {
            return insert(end(), (T(std::forward<Args>(args)...)));
        }

        template <typename... Args>
        iterator emplace_front(Args &&...args)
        {
            return insert(begin(), (T(std::forward<Args>(args)...)));
        }

        template <typename... Args>
        iterator emplace(iterator pos, Args &&...args)
        {
            return insert(pos, T(std::forward<Args>(args)...));
        }

        void push_front(const T &val = T())
        {
            insert(begin(), val);
        }

        void push_front(const T &&val)
        {
            insert(begin(), val);
        }

        void pop_back()
        {
            erase(--end());
        }

        void pop_front()
        {
            erase(begin());
        }

        iterator erase(iterator pos)
        {
            Node *next = pos.node_->next_;
            Node *prev = pos.node_->prev_;
            prev->next_ = next;
            next->prev_ = prev;
            delete pos.node_;
        }

        const T &front() const
        {
            return *(cbegin());
        }

        const T &back() const
        {
            return *(--cend());
        }

        const_iterator cbegin() const
        {
            return const_iterator(head_->next_);
        }

        const_iterator cend() const
        {
            return const_iterator(head_);
        }

        iterator begin()
        {
            return iterator(head_->next_);
        }

        iterator end()
        {
            return iterator(head_);
        }

        bool empty()
        {
            return head_->next_ == head_;
        }

        ~list()
        {
            delete head_;
        }
        
    private:
        void init()
        {
            head_ = new Node();
            head_->next_ = head_;
            head_->prev_ = head_;
        }

    private:
        Node *head_;
    };

};